Batch 3 - Class 171 - Nim Games

• [Part of lesson plan below]

• Describe the "Count to 20" Nim game to kids, with each player incrementing 1,2,3, or 4. Who wins the game?
• Let kids play amongst themselves for a while to discover the pattern
• Should you go first or second?
• What if you are counting to 21? Should you go first or second?
• Who will win if we are counting to 8132? Should you go first or second?
• What if you are allowed to increment 1, 2, 3?
• What is a general way to play this game?
• Introduce notion of winning positions if kids have not already got it
• Define winning positions, and relationship with other positions (call them "losing positions")
• Generalize to deterministic strategy games

• There are 20 pennies, with each kid able to remove 1,2,3 or 4 pennies. Player who removes the last penny wins
• See if kids can reason that this is same as Nim game
• What if we changed the rules so that the person to take the last penny loses?
• What is we can remove 1, 2 or 4 pennies at a time

• Start with a 6x8 chocolate. Break it along a line and eat one piece. Whoever eats the last piece wins
• Answer: 2x1 is a winning position to leave. For any square 3x3 or above, you can take complementary moves to leave behind a square, or if the opponent leaves less than 3 in a dimension, then leave behind a 2x1 winning position. So you should leave behind a square.

• A rook can move to left or down a 8x8 chessboard, starting at top. Player who moves last wins

• What if we had two piles of 7 and 10 counters, and each player could take a match from either or both of the two piles (Person to remove the last penny wins)

• (Mott 178) There are three piles with 3,5 and 7 counters respectively in them. At each turn, a player may draw any number of counters from one pile (or all counters from one pile). Whoever draws the last wins. Who wins and how?
• Answer: Express number of counters in each pile as powers of 2 (so first pile has 1 and 2, second has 1 and 4, third has 1, 2 and 4). If a player leaves piles so that each power of 2 is present twice across all piles combined, they will win. So in this case, the first player wins by taking 1 from any pile.
• In solution, if kids don't understand binary, do it as per comment on https://plus.maths.org/content/play-win-nim - Each power of two must have a partner